package com.zyk.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author zhangsan
 * @date 2021/5/2 11:22
 */
public class C554 {

    // 暴力解
    public static int leastBricks(List<List<Integer>> wall) {
        int R = wall.size(), C = 0;
        for (int w : wall.get(0)) {
            C += w;
        }
        int ans = R;
        for (int i = 1; i < C; i++) {   // 每个地方尝试扩
            // 看看每一层, 有没有前缀组不成 i 的
            int pre = 0;
            for (int r = 0; r < R; r++) {
                pre += across(wall.get(r), i);
            }
            ans = Math.min(ans, pre);
        }
        return ans;
    }

    // 返回前缀为target, 走过当前行需要穿过多少砖
    public static int across(List<Integer> row, int target) {
        int cnt = 0;
        for (Integer w : row) {
            cnt += w;
            if (cnt == target) {
                return 0;
            } else if (cnt > target) {
                return 1;
            }
        }
        return 1;
    }


    // 统计间隙为多少, 有多少行可以不翻墙通过.
    // 最后R-这个值, 就是间隙为它需要翻越的墙的数量, 求最小值
    public static int leastBricks2(List<List<Integer>> wall) {  // 超内存
        int C = 0;
        for (int w : wall.get(0)) C += w;
        int[] map = new int[C];
        for (List<Integer> level : wall) {
            int n = level.size() - 1, sum = 0;
            for (int i = 0; i < n; i++) {
                sum += level.get(i);
                map[sum]++;
            }
        }
        int max = 0;
        for (int value : map) {
            max = Math.max(max, value);
        }
        return wall.size() - max;
    }

    // 用数组
    public static int leastBricks3(List<List<Integer>> wall) {
        Map<Integer, Integer> map = new HashMap<>();    // 间隙为i, 有多少行可以不翻墙通过
        for (List<Integer> level : wall) {
            int n = level.size() - 1, sum = 0;
            for (int i = 0; i < n; i++) {
                sum += level.get(i);
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        int max = 0;
        for (Integer value : map.values()) {
            max = Math.max(max, value);
        }
        return wall.size() - max;
    }


    // for test
    public static void main(String[] args) {
        List<List<Integer>> wall = new ArrayList<>(); // {{1,2,2,1},{3,1,2},{1,3,2},{2,4},{3,1,2},{1,3,1,1}};
        /*wall.add(new ArrayList<>() {{
            add(100000000);
        }});
        wall.add(new ArrayList<>() {{
            add(100000000);
        }});
        wall.add(new ArrayList<>() {{
            add(100000000);
        }});
        System.out.println(leastBricks(wall));
        System.out.println(leastBricks2(wall));*/
        wall.add(new ArrayList<>() {{
            add(1);
            add(2);
            add(2);
            add(1);
        }});
        wall.add(new ArrayList<>() {{
            add(3);
            add(1);
            add(2);
        }});
        wall.add(new ArrayList<>() {{
            add(1);
            add(3);
            add(2);
        }});
        wall.add(new ArrayList<>() {{
            add(2);
            add(4);
        }});
        wall.add(new ArrayList<>() {{
            add(3);
            add(1);
            add(2);
        }});
        wall.add(new ArrayList<>() {{
            add(1);
            add(3);
            add(1);
            add(1);
        }});
        System.out.println(leastBricks(wall));
        System.out.println(leastBricks2(wall));

    }

}
